import com.sun.source.tree.Tree;

import javax.print.attribute.standard.MediaSize;
import java.util.*;

public class TestBinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val){
            this.val = val;
        }
    }

    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;

        B.left = D;
        B.right = E;

        C.left = F;
        C.right = G;

        E.right = H;

        return A;//根节点;
    }

    public void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.println(root.val + " ");
        //遍历左子树
        preOrder(root.left);
        //遍历右子树
        preOrder(root.right);
    }

    public void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        //遍历左子树
        preOrder(root.left);
        System.out.println(root.val + " ");
        //遍历右子树
        preOrder(root.right);
    }

    public void postOrder(TreeNode root){
        if(root == null){
            return;
        }
        //遍历左子树
        preOrder(root.left);
        //遍历右子树
        preOrder(root.right);
        System.out.println(root.val + " ");
    }

    public int size(TreeNode root){
        if(root == null){
            return 0;
        }
        int ret = size(root.left) + size(root.right) + 1;
        return ret;
    }

    public int getLeafNodeCount(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        int ret = getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
        return ret;
    }

    public TreeNode find(TreeNode root,char val){
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
        TreeNode ret = find(root.left,val);
        if(ret != null){
            return ret;
        }

        ret = find(root.right,val);
        if(ret != null){
            return ret;
        }
        return null;
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        //1.结构不同
        if(p == null && q != null || p != null && q == null){
            return false;
        }
        //2.结构相同，但是都为空
        if(p == null && q == null){
            return true;
        }
        //3，结构相同，值不同
        if(p.val != q.val){
            return false;
        }
        //4.此时结构相同，且都不为空

        //5.判断两棵树的左右是否同时相同
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null){
            return false;
        }
        if(isSameTree(root,subRoot)){
            return true;
        }
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        if(isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }

    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        if(root.left == null && root.right == null){
            return root;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public boolean isSymmetric(TreeNode root){
        if(root == null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }

    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
        //1. 检查结构是否相同 -> 一个为空 一个不为空
        if(leftTree != null && rightTree == null || leftTree == null && rightTree != null){
            return false;
        }
        //2. 检查结构是否相同 -> 处理 【两个都为空】 和 两个都不为空
        if(leftTree == null && rightTree == null){
            return true;
        }
        //3. 检查结构是否相同 -> 处理 两个都为空 和 【两个都不为空，判断值一样吗】
        if(leftTree.val != rightTree.val){
            return false;
        }
        //4. 此时两个引用 都不为空 同时 节点的值一样
        //5. 开始判断是否对称
        //6. 满足 左子树的左  和  右子树的 右对称  同时 左子树的右  和 右子树的左 对称
        return isSymmetricChild(leftTree.left,rightTree.right) && isSymmetricChild(leftTree.right,rightTree.left);
    }

    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }

        int leftH = maxDepth(root.left);
        int rightH = maxDepth(root.right);

        return Math.abs(leftH - rightH) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);

        return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
    }

    //二叉树创建和遍历
//    class TreeNode{
//        public char val;
//        public TreeNode left;
//        public TreeNode right;
//
//        public TreeNode (char val){
//            this.val = val;
//        }
//    }
//
//    public class Main {
//
//        public static int i = 0;
//
//        public static TreeNode createTree(String str){
//            TreeNode root = null;
//            if(str.charAt(i) != '#'){
//                root = new TreeNode(str.charAt(i));
//                i++;
//                root.left = createTree(str);
//                root.right = createTree(str);
//            } else{
//                i++;
//            }
//            return root;
//        }
//
//        public static void inorder(TreeNode root){
//            if(root == null){
//                return;
//            }
//            inorder(root.left);
//            System.out.print(root.val + " ");
//            inorder(root.right);
//        }
//
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            // 注意 hasNext 和 hasNextLine 的区别
//            while (in.hasNextLine()) { // 注意 while 处理多个 case
//                String str = in.nextLine();
//                TreeNode root = createTree(str);
//                inorder(root);
//            }
//        }
//    }

    //二叉树层序遍历
    public void levelOrder1(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null){
            return;
        }
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }

    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while (size > 0){
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> levelRet = new ArrayList<>();
        if(root == null){
            return levelRet;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            List<Integer> level = new ArrayList<>();
            int size = queue.size();
            while (size > 0){
                TreeNode cur = queue.poll();
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
                size--;
                level.add(cur.val);
            }
            levelRet.add(0,level);
        }
        return levelRet;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        if(root == p || root == q){
            return root;
        }
        TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
        TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
        //两边都不为空
        if(leftNode != null && rightNode != null){
            return root;
        }else if(leftNode != null){
            //左不为空
            return leftNode;
        }else{
            return rightNode;
        }
    }

    //非递归前序遍历
    public void preorderTraversal1(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }

            TreeNode top = stack.pop();
            cur = top.right;
        }
    }

    public List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
//                System.out.print(cur.val + " ");
                result.add(cur.val);
                cur = cur.left;
            }

            TreeNode top = stack.pop();
            cur = top.right;
        }
        return result;
    }

    //非递归中序遍历
    public void inorderTraversal1(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            TreeNode top = stack.pop();
            System.out.print(top.val + " ");
            cur = top.right;
        }
    }

    public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            TreeNode top = stack.pop();
//            System.out.print(top.val + " ");
            result.add(top.val);
            cur = top.right;
        }
        return result;
    }

    //非递归后序遍历
    public void postorderTraversal1(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            TreeNode top = stack.peek();
            if (top.right == null || top.right == prev) {
                stack.pop();
                System.out.println(top.val + " ");
                prev = top;
            } else {
                cur = top.right;
            }
        }
    }

    public List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            TreeNode top = stack.peek();
            if (top.right == null || top.right == prev) {
                stack.pop();
//                System.out.println(top.val + " ");
                result.add(top.val);
                prev = top;
            } else {
                cur = top.right;
            }
        }
        return result;
    }

    public String tree2str(TreeNode root) {
        // 如果根节点为空，则返回空字符串
        if (root == null) {
            return "";
        }
        // 如果根节点没有左右子节点，则返回根节点的值
        if (root.left == null && root.right == null) {
            return Integer.toString(root.val);
        }
        // 如果只有左子树，则返回根节点值和左子树的字符串表示
        if (root.right == null) {
            return new StringBuffer().append(root.val).append("(").append(tree2str(root.left)).append(")").toString();
        }
        // 否则，返回根节点值和左右子树的字符串表示
        return new StringBuffer().append(root.val).append("(").append(tree2str(root.left)).append(")(").append(tree2str(root.right)).append(")").toString();
    }

    class Solution1 {
        public int preIndex;

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return buildTreeChilde(preorder,inorder,0,inorder.length-1);
        }

        private TreeNode buildTreeChilde(int[] preorder, int[] inorder, int inBegin, int inEnd) {
            if(inBegin > inEnd){
                return null;
            }
            TreeNode root = new TreeNode(preorder[preIndex]);

            int rootIndex = findRootIndex(inorder,inBegin,inEnd,preorder[preIndex]);

            preIndex++;

            root.left = buildTreeChilde(preorder,inorder,inBegin,rootIndex-1);
            root.right = buildTreeChilde(preorder,inorder,rootIndex+1,inEnd);

            return root;
        }

        private int findRootIndex(int[] inorder, int inBegin, int inEnd, int key){
            for (int i = inBegin; i <= inEnd; i++) {
                if (key == inorder[i]) {
                    return i;
                }
            }
            return -1;
        }

    }

    class Solution2 {
        public int postIndex = 0;

        public TreeNode buildTree(int[] inorder, int[] postorder) {
            postIndex = postorder.length-1;
            return buildTreeChilde(inorder,postorder,0,inorder.length-1);
        }

        private TreeNode buildTreeChilde(int[] inorder, int[] postorder, int inBegin, int inEnd) {
            if(inBegin > inEnd){
                return null;
            }
            TreeNode root = new TreeNode(postorder[postIndex]);

            int rootIndex = findRootIndex(inorder,inBegin,inEnd,postorder[postIndex]);

            postIndex--;

            root.right = buildTreeChilde(inorder,postorder,rootIndex+1,inEnd);
            root.left = buildTreeChilde(inorder,postorder,inBegin,rootIndex-1);

            return root;
        }

        private int findRootIndex(int[] inorder, int inBegin, int inEnd, int key){
            for (int i = inBegin; i <= inEnd; i++) {
                if (key == inorder[i]) {
                    return i;
                }
            }
            return -1;
        }

    }

}
